//	  Albert'sLogicPuzzle
//
//有5个具有不同颜色的房间，每个房间住着一个不同国籍的人，每个人都喝一种特定品牌的饮料，抽一特定品牌的香烟，养一个特定的宠物
//没有任意的两个人抽相同品牌的香烟、或喝相同品牌的饮料、或养相同的宠物。那么已知：
//1.英国人住红房子
//2.瑞典人养狗
//3.丹麦人喝茶
//4.绿房子紧挨着白房子，在白房子左边
//5.绿房子主人喝咖啡
//6.抽PALL MALL香烟的人养鸟
//7.黄房子的人抽DUNHILL香烟
//8.中间房子的人喝牛奶
//9.挪威人住第一个房子（最左边）
//10.抽BLENDS香烟的人和养猫的人相邻
//11.养马的人和抽DUNHILL香烟的人相邻
//12.抽BLUEMASTER牌香烟的人喝啤酒
//13.德国人抽PRINCE香烟
//14.挪威人和住蓝房子的人相邻
//15.抽BLENDS香烟的人和喝矿泉水的人相邻
//问：谁在养鱼
//核心思想使用回溯法递归遍历条件树，遇到不合题意的分支可以直接回溯避免无谓的遍历，从而大大加快遍历速度。
//运行时间小于1s

#include <iostream>
#include <vector>

//英国(0)、瑞典(1)、丹麦(2)、挪威(3)、德国(4)
int person[5] {0,1,2,3,4};
//绿色(0)、白色(1)、蓝色(2)、黄色(3)、红色(4)
int color[5] {0,1,2,3,4};
//茶(0)、咖啡(1)、牛奶(2)、啤酒(3)、矿泉水(4)
int beverage[5] {0,1,2,3,4};
//猫(0)、马(1)、鸟(2)、狗(3)、鱼(4)
int pet[5] {0,1,2,3,4};
//PM(0)、DU(1)、BLENDS(2)、BLUEMASTER(3)、PRINCE(4)
int brand[5] {0,1,2,3,4};

void backtrack_person(int, int);
void backtrack_beverage(int, int);
void backtrack_pet(int, int);
void backtrack_brand(int, int);
void backtrack_color(int, int);

void swap(int*, int*);
bool judge();
void print_fish();

int main(int argc, const char * argv[]) {
	backtrack_person(0, 4);
	print_fish();
    return 0;
}

void swap(int *i, int *j)
{
	int temp = 0;
	temp = *i;
	*i = *j;
	*j = temp;
}

void backtrack_person( int i, int j)
{
	if(i == j)
		return;
	for(int x = i; x <= j; ++x)
	{
		if(judge())
			return;
		else
		{
			backtrack_color(0, 4);
			swap(&person[x], &person[i]);
			backtrack_person(i + 1, j);
			swap(&person[x], &person[i]);
		}
	}
}
void backtrack_color( int i, int j)
{
	if(i == j)
		return;
	for(int x = i; x <= j; ++x)
	{
		if(judge())
			return;
		else
		{
			backtrack_pet(0, 4);
			swap(&color[x], &color[i]);
			backtrack_color(i + 1, j);
			swap(&color[x], &color[i]);
		}
	}
}
void backtrack_brand( int i, int j)
{
	if(i == j)
		return;
	for(int x = i; x <= j; ++x)
	{
		if(judge())
			return;
		else
		{
			backtrack_beverage(0, 4);
			swap(&brand[x], &brand[i]);
			backtrack_brand(i + 1, j);
			swap(&brand[x], &brand[i]);
		}
	}
}
void backtrack_beverage( int i, int j)
{
	if(i == j)
		return;
	for(int x = i; x <= j; ++x)
	{
		if(judge())
			return;
		else
		{
			backtrack_pet(0, 4);
			swap(&beverage[x], &beverage[i]);
			backtrack_beverage(i + 1, j);
			swap(&beverage[x], &beverage[i]);
		}
	}
}
void backtrack_pet( int i, int j)
{
	if(i == j)
		return;
	for(int x = i; x <= j; ++x)
	{
		if(judge())
			return;
		else
		{
			swap(&pet[x], &pet[i]);
			backtrack_pet(i + 1, j);
			swap(&pet[x], &pet[i]);
		}
	}
}

bool judge()
{
	int english = 0, swedish = 0, dane = 0, norse = 0, german = 0;
	int green = 0, white = 0, blue = 0, yellow = 0, red = 0;
	int tea = 0, coffe = 0, milk = 0, beer = 0, water = 0;
	int cat = 0, horse = 0, bird = 0, dog = 0, fish = 0;
	int PM = 0, DU = 0, BLENDS = 0, BLUMASTER = 0, PRINCE = 0;
	for(int i = 0; i < 5; ++i)
	{
		if(brand[i] == 0)
			PM = i;
		else if(brand[i] == 1)
			DU = i;
		else if(brand[i] == 2)
			BLENDS = i;
		else if(brand[i] == 3)
			BLUMASTER = i;
		else PRINCE = i;
	}
	for(int i = 0; i < 5; ++i)
	{
		if(pet[i] == 0)
			cat = i;
		else if(pet[i] == 1)
			horse = i;
		else if(pet[i] == 2)
			bird = i;
		else if(pet[i] == 3)
			dog = i;
		else fish = i;
	}
	for(int i = 0; i < 5; ++i)
	{
		if(beverage[i] == 0)
			tea = i;
		else if(beverage[i] == 1)
			coffe = i;
		else if(beverage[i] == 2)
			milk = i;
		else if(beverage[i] == 3)
			beer = i;
		else water = i;
	}
	for(int i = 0; i < 5; ++i)
	{
		if(person[i] == 0)
			english = i;
		else if(person[i] == 1)
			swedish = i;
		else if(person[i] == 2)
			dane = i;
		else if(person[i] == 3)
			norse = i;
		else german = i;
	}
	for(int i = 0; i < 5; ++i)
	{
		if(color[i] == 0)
			green = i;
		else if(color[i] == 1)
			white = i;
		else if(color[i] == 2)
			blue = i;
		else if(color[i] == 3)
			yellow = i;
		else red = i;
	}
	
	if((english == red) && (swedish == dog) && (dane == tea) && ((green + 1) == white)  && (green == coffe) && (PM == bird) && (yellow == DU) && (milk == 2) && (norse == 0) && (((BLENDS+1)==cat) || (BLENDS-1) == cat) && (((horse + 1) == DU) || ((horse - 1) == DU)) && (BLUMASTER == beer) && (german == PRINCE) && (((norse + 1) == blue) || ((norse - 1) == blue)) && (((BLENDS + 1) == water) || ((BLENDS - 1) == water)))
		return true;
	else
		return false;
}

void print_fish()
{
	for(int i = 0; i < 5; ++i)
		if(pet[i] == 4)
		{
			switch (i) {
				case 0:
					std::cout << "English" << std::endl;
					break;
				case 1:
					std::cout << "Swedish" << std::endl;
					break;
				case 2:
					std::cout << "Dane" << std::endl;
					break;
				case 3:
					std::cout << "Norse" << std::endl;
					break;
				case 4:
					std::cout << "German" << std::endl;
					break;
				default:
					std::cout << "False" << std::endl;
					break;
			}
			break;
		}
}
